package com.leetcode.LC_MED;

import java.util.ArrayList;
import java.util.List;

public class LC129 {
    public int sumNumbers(TreeNode root) {

        ArrayList<Integer> list = new ArrayList<>();
        dfs(root, list, new StringBuilder());
        int sum = 0;
        for (Integer integer : list) {
            sum += integer;
        }
        return sum;

    }

    private void dfs(TreeNode root, List<Integer> list, StringBuilder sb) {
        //sum为各个路径的数字
        if (root == null) {
            return;
        }
        sb.append(root.val);
        if (root.right == null && root.left == null) {
            list.add(Integer.valueOf(sb.toString()));
        }

        dfs(root.left, list, sb);
        dfs(root.right, list, sb);
        sb.deleteCharAt(sb.length() - 1);
    }

    private void dfs_2(TreeNode root, int chain, int[] res) {
        if (root.left == null && root.right == null) {
            res[0] += chain;
            return;
        }
        if (root.left != null) {
            dfs_2(root.left, chain*10+root.left.val, res);
        }
        if (root.right != null) {
            dfs_2(root.right, chain*10+root.right.val, res);
        }
    }
}
